# -*- coding:utf8 -*-
#by liuqjox
## 加载包
from __future__ import print_function

class Edit_Distance(object):
    '''
    编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
    许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
    '''

    def __init__(self):      
        print("Caculating edit distance...")

    def min_edit_dist(self, sm, sn):
        '''
        reference url: http://blog.csdn.net/chichoxian/article/details/53944188
        :param sm: first sentence
        :param sn: second sentence
        :return: the distance between this two sentences
        '''
        #sm = sm.decode('utf8')
        #sn = sn.decode('utf8')
        m, n = len(sm) + 1, len(sn) + 1

        '''create a matrix (m*n) and set its default value '''
        matrix = [[0] * n for i in range(m)]
        matrix[0][0] = 0
        for i in range(1, m):
            matrix[i][0] = matrix[i - 1][0] + 1
        for j in range(1, n):
            matrix[0][j] = matrix[0][j - 1] + 1
            
        '''
        for i in range(m):
            print(matrix[i])

        print("********************")
        '''

        '''calculate the matrix (m*n) and return edit distance '''
        for i in range(1, m):
            for j in range(1, n):
                if sm[i - 1] == sn[j - 1]:
                    cost = 0
                else:
                    cost = 1
                matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost)
                #print("i=",i,"j=",j,"m[i,j]=",matrix[i][j],'cost=',cost,"sm=",sm[i-1],"sn=",sn[j-1],matrix[i - 1][j - 1] + cost)
        '''
        for i in range(m):
            print(matrix[i])
        '''
        return matrix[m - 1][n - 1]

def syn_change(sm,sn,syn):
    l=0
    while l<len(syn):
        i=syn[l]        
        flag_sn=sn.find(i[1])
        if (i[0] in sm) and (i[1] in sn):
            sn=sn[:flag_sn]+i[0]+sn[flag_sn+len(i[1]):]
            #new=sm[:flag]+sm[flag:flag+len(i[0])]+sm[flag+len(i[0]):]            
            l=l-1
        l=l+1           
    return sn

def test_min_edit_dist():
    syn=[['USA','America'],['love','like'],['hate','dislike']]
    sm='I love China.I love USA.'
    sn='I like China.I like America too.'
    print('Original input...')
    print(sm)
    print(sn)
    sn=syn_change(sm,sn,syn)
    print('Unifying synonyms...')
    print(sm)
    print(sn)
    edit_distance = Edit_Distance()    
    mindist = edit_distance.min_edit_dist(sm,sn)    
    print('Edit Distance is',mindist)

if __name__ == '__main__':
    test_min_edit_dist()